package July.GenerateTrees;

import java.util.ArrayList;
import java.util.List;

//95. 不同的二叉搜索树 II
public class GenerateTrees {
    public static void main(String[] args) {
        Solution s = new Solution();
        s.generateTrees(3);
    }
}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution { 
    public List<TreeNode> generateTrees(int n) {
        if(n==0) return new ArrayList<>();
        List<TreeNode> ansList = gen(1, n+1);
        return ansList;
    }

    private List<TreeNode> gen(int start,int end){
        if(start>=end) return null;
        List<TreeNode> list = new ArrayList<>();
        for (int i = start; i < end; i++) {
                List<TreeNode> leftL = gen(start, i); 
                List<TreeNode> rightR =gen(i+1,end);
                if(leftL!=null){
                    if(rightR!=null){
                        for (TreeNode treeNode : rightR) {
                            for (TreeNode treeNode2 : leftL) {
                                TreeNode r = new TreeNode(i);
                                r.left = treeNode2;
                                r.right =treeNode;
                                list.add(r);
                            }
                        }
                    }
                    else{
                        for (TreeNode treeNode2 : leftL) {
                            TreeNode r = new TreeNode(i);
                            r.left = treeNode2;
                            r.right =null;
                            list.add(r);
                        }
                    }
                }else{
                    if(rightR!=null){
                        for (TreeNode treeNode2 : rightR) {
                            TreeNode r = new TreeNode(i);
                            r.left = null;
                            r.right =treeNode2;
                            list.add(r);
                        }
                    }
                    else{
                        TreeNode r = new TreeNode(i);
                            r.left = null;
                            r.right =null;
                            list.add(r);
                    }
                }
        }
        return list;
    }
}